|
In the mathematical discipline of graph theory, the Erdős–Pósa theorem, named after Paul Erdős and Lajos Pósa, states that there is a function such that for each positive integer , every graph either contains vertex-disjoint circuits or it has a feedback vertex set of vertices that intersects every circuit. Furthermore, in the sense of Big O notation. Because of this theorem, circuits are said to ''have the Erdős–Pósa property''. The theorem claims that for any finite number there is an appropriate (least) value , with the property that every graph with no vertex-disjoint circuits all circuits can be covered by vertices. This generalized an unpublished result of Béla Bollobás, which states that . obtained the bounds for the general case. The result suggests that although there are infinitely many different graphs with no disjoint circuits, they split into finitely many simply describable classes. For the case , gave a complete characterization. proved and . ==Erdős–Pósa property== A family of graphs or hypergraphs is defined to have the Erdős–Pósa property if there exists a function such that for every (hyper-)graph and every integer one of the following is true: * contains vertex-disjoint subgraphs each isomorphic to a graph in ; or * contains a vertex set of size at most such that has no subgraph isomorphic to a graph in . The definition is often phrased as follows. If one denotes by the maximum number of vertex disjoint subgraphs of isomorphic to a graph in and by the minimum number of vertices whose deletion from leaves a graph without a subgraph isomorphic to a graph in , then , for some function not depending on . 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Erdős–Pósa theorem」の詳細全文を読む スポンサード リンク
|